10365. Цепочки ромашек

Каждый день, прогуливаясь по ферме, корова Бесси посещает свое любимое пастбище, на котором растут n цветков (все разноцветные ромашки), пронумерованные от 1 до n и выстроенные в ряд. Цветок i имеет p_i лепестков.

Будучи начинающим фотографом, Бесси решила сделать несколько снимков этих цветков. В частности, для каждой пары цветков (i, j), удовлетворяющих 1 ≤ i ≤ j ≤ n, Бесси делает снимок всех цветков от i до j (включая i и j).

Позже Бесси смотрит на эти фотографии и замечает, что на некоторых из них присутствует “средний цветок” – цветок с p лепестками, где p – среднее количество лепестков среди всех цветков на фотографии.

На скольких фотографиях Бесси присутствует средний цветок?

Вход. Первая строка содержит число n (1 ≤ n ≤ 100). Вторая строка содержит n целых чисел p₁, ..., p_n (1 ≤ p_i ≤ 1000).

Выход. Выведите количество фотографий, на которых изображен средний цветок.

Пример. Каждая фотография, содержащая в точности один цветок, участвует в подсчете (в примере их четыре). Кроме того, отрезки (1, 2) и (2, 4) соответствуют фотографиям, которые содержат средний цветок.

Пример входа	Пример выхода
4 1 1 2 3	6

РЕШЕНИЕ

перебор

Анализ алгоритма

Решение за O(n³). Переберем все возможные интервалы [i; j] (0 ≤ i ≤ j < n) и проверим, принадлежит ли ему средний цветок. Для этого должно существовать такое p_k (i ≤ k ≤ j), что

p_k = totalPetals / (j – i + 1),

где totalPetals – общее количество лепестков в цветках на интервале [i; j].

Реализация алгоритма – O(n³)

Объявим массив для хранения количества лепестков p_i в цветках.

#define MAX 101

int p[MAX];

Читаем входные данные.

scanf("%d", &n);

for (i = 0; i < n; i++)

scanf("%d", &p[i]);

Количество фотографий, на которых изображен средний цветок, подсчитываем в переменной photos.

photos = 0;

Перебираем все возможные интервалы [i; j] (0 ≤ i ≤ j < n). Проверяем, лежит ли на нем среднее арифметическое лепестков всех цветков этого интервала.

for (i = 0; i < n; i++)

for (j = i; j < n; j++)

{

В переменной totalPetals вычисляем количество лепестков в цветках на интервале [i; j].

int totalPetals = 0;

for (k = i; k <= j; k++)

totalPetals += p[k];

Перебираем числа p_k на интервале [i; j] (i ≤ k ≤ j). Если p_k является средним арифметическим количества лепестков среди всех цветков на фотографии в интервале [i; j], то увеличиваем photos на 1. Для этого должно выполняться соотношение:

p_k = totalPetals / (j – i + 1)

present = 0;

for (int k = i; k <= j; k++)

if (p[k] * (j - i + 1) == totalPetals) present = 1;

if (present) photos++;

}

Выводим ответ.

printf("%d\n", photos);